package com.liukunup.distance;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.NonNull;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang3.StringUtils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 编辑距离 EditDistance
 * 又称 Levenshtein Distance
 *
 * 使用示例
 * public static void main(String[] args) {
 *     Text text = new Text("abcdfh", "adcedh");
 *     int minEditDistance = calc(text);
 *     log.info("Result: {}", text);
 * }
 *
 * @author Liu Kun
 * @date 2021-04-03 20:26:05
 * see https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
 **/
@Slf4j
public class EditDistance {

    public static final String OP_INSERT = "op_insert";
    public static final String OP_DELETE = "op_delete";
    public static final String OP_REPLACE = "op_replace";

    public static int calc(@NonNull Text text) {
        // 检查 源串&目标串
        String src = text.getSrc();
        String dst = text.getDst();
        if (StringUtils.isEmpty(src) && StringUtils.isEmpty(dst)) {
            text.setDistance(0);
            text.setOps(null);
            return 0;
        } else {
            if (StringUtils.isEmpty(src)) {
                int len = dst.length();
                text.setDistance(len);
                Map<Integer, List<String>> ops = new HashMap<>(len);
                for (int i = 0; i < len; i++) {
                    ops.put(i, Arrays.asList(OP_INSERT, src, String.valueOf(dst.charAt(i))));
                }
                text.setOps(ops);
                return len;
            }
            if (StringUtils.isEmpty(dst)) {
                int len = src.length();
                text.setDistance(len);
                Map<Integer, List<String>> ops = new HashMap<>(len);
                for (int i = 0; i < len; i++) {
                    ops.put(i, Arrays.asList(OP_DELETE, String.valueOf(src.charAt(i)), dst));
                }
                text.setOps(ops);
                return len;
            }
        }

        // 计算dp数组
        int[][] dp = dpSolve(src, dst);

        // 获取 源串&目标串 的长度
        int n = src.length();
        int m = dst.length();
        // 获取编辑距离
        int minEditDistance = dp[n][m];

        // 获取编辑距离并保存
        text.setDistance(minEditDistance);

        // 路径回溯
        pathBacktrack(dp, text);

        return minEditDistance;
    }

    /**
     * 采用动态规划来解决
     * @param src 源串 (保证非null且非空串)
     * @param dst 目标串 (保证非null且非空串)
     * @return dp数组
     */
    private static int[][] dpSolve(@NonNull String src, @NonNull String dst) {

        // 获取 源串&目标串 的长度
        int n = src.length();
        int m = dst.length();

        // DP 数组
        int[][] dp = new int[n + 1][m + 1];

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            dp[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = dp[i - 1][j] + 1;
                int down = dp[i][j - 1] + 1;
                int leftDown = dp[i - 1][j - 1];
                if (src.charAt(i - 1) != dst.charAt(j - 1)) {
                    leftDown += 1;
                }
                dp[i][j] = Math.min(left, Math.min(down, leftDown));
            }
        }

        return dp;
    }

    /**
     * 回溯路径
     * @param dp dp数组
     * @param text 文本对象
     */
    private static void pathBacktrack(@NonNull int[][] dp, @NonNull Text text) {
        // 获取 源串&目标串
        String src = text.getSrc();
        String dst = text.getDst();

        // 获取 源串&目标串 的长度
        int n = src.length();
        int m = dst.length();

        // 记录编辑操作
        Map<Integer, List<String>> ops = new HashMap<>(text.getDistance());

        // 路径回溯过程
        // n src 横行 / m dst 竖列
        while (n >= 0 || m >= 0) {
            // 往上走 插入
            if (m > 0 && dp[n][m - 1] + 1 == dp[n][m]) {
                ops.put(n - 1, Arrays.asList(OP_INSERT,
                        null,
                        String.valueOf(dst.charAt(m - 1))));
                m -= 1;
                continue;
            }
            // 往左走 删除
            if (n > 0 && dp[n - 1][m] + 1 == dp[n][m]) {
                ops.put(n - 1, Arrays.asList(OP_DELETE,
                        String.valueOf(src.charAt(n - 1)),
                        null));
                n -= 1;
                continue;
            }
            // 往斜向左上走 替换
            if (n > 0 && m > 0 && dp[n - 1][m - 1] + 1 == dp[n][m]) {
                ops.put(n - 1, Arrays.asList(OP_REPLACE,
                        String.valueOf(src.charAt(n - 1)),
                        String.valueOf(dst.charAt(m - 1))));
                m -= 1;
                n -= 1;
                continue;
            }
            // 往斜向左上走 未发生编辑操作
            if (n > 0 && m > 0 && dp[n - 1][m - 1] == dp[n][m]) {
            }
            m -= 1;
            n -= 1;
        }

        text.setOps(ops);
    }

    @Data
    @NoArgsConstructor
    @AllArgsConstructor
    public static class Text {
        /**
         * 源串
         */
        private String src;
        /**
         * 目标串
         */
        private String dst;
        /**
         * 编辑距离
         */
        private int distance;
        /**
         * 操作标识
         * 相对于源串
         * 格式: 下标值, 操作,源,目标
         *
         * 插入: 在此下标值位置之后插入
         * 删除: 在此下标值位置删除
         * 替换: 在此下标值位置替换
         */
        private Map<Integer, List<String>> ops;
        /**
         * 构造作为计算入参
         * @param src 源串
         * @param dst 目标串
         */
        public Text(String src, String dst) {
            this.src = src;
            this.dst = dst;
        }
    }
}